package 在排序数组中查找元素的第一个和最后一个位置;

class Solution {
    //暴力解法
    public int[] searchRange1(int[] nums, int target) {
        int begin = -1;
        int end = -1;
        int len = nums.length;
        for(int i = 0; i < len; i++){
            if(nums[i] == target && begin == -1){
                begin = i;
            }
            if(nums[i] == target){
                end = i;
            }
        }
        return new int[]{begin,end};
    }

    //二分查找算法
    public int[] searchRange(int[] nums, int target) {
        int begin = -1;
        int end = -1;
        int len = nums.length;
        int left = 0,right = len - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        if(len != 0 && nums[right] == target){
            begin = right;
        }
        left = 0;
        right = len - 1;
        while(left < right){
            int mid = left + (right - left) / 2 + 1;
            if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid;
            }
        }
        if(len != 0 && nums[right] == target){
            end = right;
        }
        return new int[]{begin,end};
    }
}